package Graph.graphWithWeight.ShortestPath.BellmanFord;

import Graph.graphWithWeight.GraphWeight;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * @Author: 蔡翔
 * @Date: 2020/3/21 21:17
 * @Version 1.0
 *
 * BellmanFord 是 有向图 算法
 */
public class BellmanFord {
    private GraphWeight G;
    //原点
    private int s;
    private int[] dis;
    private boolean hasNegativeCycle = false;

    private int[] pre;

    public BellmanFord(GraphWeight G,int s){
        this.G = G;
        G.validateVertex(s);
        this.s = s;

        dis = new int[G.V()];
        Arrays.fill(dis,Integer.MAX_VALUE);
        dis[s] =0;

        pre = new int[G.V()];
        Arrays.fill(pre,-1);
        //pre[s] = s;


        //循环做v-1轮的 “松弛操作” ,所以pass 从 1 开始
        // (之所以要做v-1次是因为 在开始前几次由于dis[v] == Integer.MAX_VALUE 可能造成 未进行最终“真实松弛操作”，
        // 而pass==1 这第一次必定原点会进行松弛操作，，所以要使所有的顶点v 都确保进行松弛操作，所以需要v-1 次 整体循环。v-1次是最坏情况。)
        for(int pass = 1;pass<G.V();pass++){
            //每次循环都对所有的边进行松弛操作
            for(int v = 0;v<G.V();v++){
                for(int w:G.adj(v)){
                    //这就是松弛操作   ，如果dis【v】是一个无穷，dis[w]也是无穷 那么久无法比较了 所以要加dis[v] != Integer.MAX_VALUE
                    //不需要对dis[w] 做非无穷判断 因为，dis[v]+具体的数<无穷 是合法的。
                    if(dis[v]+G.getWeight(v,w)<dis[w] && dis[v] != Integer.MAX_VALUE){
                        dis[w] = dis[v]+G.getWeight(v,w);
                        pre[w] = v;
                    }
                }
            }
        }

        //松弛操作完了之后再来一轮松弛操作
        for(int v = 0;v<G.V();v++){
            for(int w:G.adj(v)){
                if(dis[v]+G.getWeight(v,w)<dis[w] && dis[v] != Integer.MAX_VALUE){
                    //如果再次 松弛操作仍然 进入了这个if，那么说明 是有负权环的
                    hasNegativeCycle = true;
                }
            }
        }
    }

    public boolean hasNegativeCycle(){
        return hasNegativeCycle;
    }

    public boolean isConnectedTo(int v){
        G.validateVertex(v);
        return dis[v] != Integer.MAX_VALUE;
    }

    public int disTo(int v){
        G.validateVertex(v);
        if(hasNegativeCycle){
            throw new RuntimeException("exist negative cycle.");
        }
        return dis[v];
    }

    //原点s 到t
    public Iterable<Integer> path(int t){
        ArrayList<Integer> res = new ArrayList<>();
        if(!isConnectedTo(t)){
            return res;
        }
        int cur = t;
        while (cur!=s){
            res.add(cur);
            cur = pre[cur];
        }
        res.add(s);
        Collections.reverse(res);
        return res;
    }

    public static void main(String[] args) {
        GraphWeight weight = new GraphWeight("gDjjkstra.txt");
        BellmanFord bellmanFord = new BellmanFord(weight,0);
        if(!bellmanFord.hasNegativeCycle()){
            for(int v=0;v<weight.V();v++){
                System.out.println(bellmanFord.disTo(v)+"  ");
            }
            System.out.println(bellmanFord.path(3));
        }else {
            System.out.println("exist negative cycle");
        }

    }
}
